1. Field of the Invention
The present invention relates to high-speed sorting in a sorting system and more specifically to a selector based high-speed sorting method and apparatus wherein a large amount of data can be processed at high speed.
2. Description of the Related Art
FIG. 16 shows an overall block diagram of a conventional sorting system which includes a hardware merge sorter of a conventional art disclosed in Japan Unexamined Patent Publication No.86043/1988.
The sorting system in FIG. 16 has a hardware merge sorter 22, an external memory or disk unit 30, a disk controller 31, a system controller 41 and a channel interface 42. Referring to the figure, a common data bus 40 transfers data between the system controller 41 and the channel interface 42. A data bus 43 transfers data between the channel interface 42 and a host computer. A data bus 32 transfers data between the disk unit 30 and the disk controller 31. A data bus 34 transfers data between the disk controller 31 and the common data bus 40. A sort data input bus 33 transfers sort data to the hardware merge sorter 22. A sorted data output bus 35 transfers sorted data from the hardware merge sorter 22 to the common data bus 40. The hardware merge sorter 22 has linearly ordered and cascaded in series n number of pipeline stages. Each pipeline stage has a sort element or local processor and a responsive private memory or local memory coupled to the local processor. Specifically, the first pipeline stage has a local processor P.sub.1 1 and a local memory M.sub.1 11 with a storage capacity of one (2.sup.0) record; the second pipeline stage has a local processor P.sub.2 2 and a local memory M.sub.2 12 with a storage capacity of two (2.sup.1) records; the third pipeline stage has a local processor P.sub.3 3 and a local memory M.sub.3 13 with a storage capacity of four (2.sup.2) records, and so on through the last pipeline stage having a local processor P.sub.n 6 and a local memory M.sub.n 16 with a storage capacity of 2.sup.n-1 number of records. Each local processor is provided with an internal buffer. A line buffer is provided between neighboring local processors.
FIG. 17 shows a simplified block diagram of the conventional sorting system in FIG. 16. Referring to the figure, a local memory bus 106 transfers data between the local processor and the respective local memory in any pipeline stage of the hardware merge sorter 22. A sort controller 100 is a multi-functional unit which includes a large-scale buffer, the disk unit 30, the system controller 41, the disk controller 31, and a general-purpose processor.
Referring to FIG. 16, a stream of data to be sorted is read out by the disk controller 31 from the disk unit 30 and is generally transferred to the hardware merge sorter 22 through the data bus 32 and the sort data input bus 33. Otherwise, the stream of data is transferred to the host computer via the system controller 41 and the channel interface 42 and then travels back again to the disk controller 31 to be input to the hardware merge sorter 22 via the channel interface 42 and the system controller 41.
When the hardware merge sorter 22 receives sort data, the local processors P.sub.1 1 through P.sub.n 6, together with the responsive local memories M.sub.1 11 through M.sub.n 16, perform a series of pipeline merge sort operations. When the input data have been sorted through the pipeline stages, the resulting string of sorted data are output from the hardware merge sorter 22 to the common data bus 40 through the sorted data output bus 35. The stream of sorted data can then be transferred to the system controller 41 or to the host computer via the channel interface 42 through the data bus 43.
According to the conventional art, the conventional hardware merge sorter 22 in FIG. 16 or 17 can sort N (N.ltoreq.2.sup.n, with n as an integer) records with the n pipeline stages involving the local processors and local memories. The conventional hardware merge sorter 22 sorts data on a two-way merge basis. N number of records are serially input to the local processor P.sub.1 1 and through the pipeline stages, such that the records are put in order and a string of N sorted records is output. A two-way merge sort inputs and processes two strings of records stored in the storage units of the local memory and the internal buffer in each pipeline stage. When completing a two-way merge sort operation, the local processor transfers the resulting string of sorted records to the next local processor in the pipeline stage. For example, a local memory M.sub.i responsive to the local processor P.sub.i has a storage capacity of 2.sup.i-1 number of records. The local processor P.sub.i receives two strings of 2.sup.i-1 records consecutively from a local processor P.sub.i-1 in the preceding pipeline stage and merges the two strings of records into a string of sorted 2.sup.i number of records. The string of sorted 2.sup.i number of records is output to a local processor P.sub.i+1 in the contiguous pipeline stage for a further merge sort.
The basic operation of a two-way merge sort is now described in more detail in accordance with the conventional art in reference to FIG. 16 or 17. The operation has two phases of operation, a storage phase and a merge sort phase. The storage phase is a preliminary phase for the merge sort phase. In the storage phase, two strings of sorted records transferred consecutively from a preceding local processor in the pipeline stage are input to the local processor and are stored in the responsive local memory and the internal buffer respectively. In the merge sort phase, the local processor inputs one record, from each of the two stored strings, at a time for comparison. The pair of records are compared and put in order according to a given requirement. For example the records may be sorted in descending order from a highest initial value or in the ascending order from a lowest initial value. As a result, a record in an earlier order of the two is output from the local processor to be merged into a string of sorted records in the line buffer as a pipeline segment. The merge sort operation is repeated in this manner until there are no more records remaining in either storage units so that the resulting string of records are in order. The resulting string of sorted records are then transferred to the next local processor in the pipeline stage for a further merge sort. Thus, a two-way merge sort according to the conventional art doubles the amount of data in each pipeline stage by merging a pair of strings of records into a single string of sorted records.
FIG. 18 shows a conceptual diagram illustrating a series of the conventional pipeline merge sort operations according to the conventional sorting method. In the figure, a shaded triangle, actually with an exponential curve, illustrates the storage of the local memories and the shaded cubes are the sort elements or the local processors. According to FIG. 18, a stream of sort data is serially input in the local processor P.sub.1 1, processed through a series of the conventional merge sort operations and output in a resulting string of sorted data from the local processor P.sub.1 1. An accomplished string of sorted data is transferred to the sort controller.
With reference to a two-way merge sort, a string of sorted records in storage loses a heading record when the heading record is output for comparison to the local processor. The input order of a heading record in the local processor is random between the storage units depending upon the comparison result. To maintain the serial operation of outputting a heading record of a sorted string in storage, a heading address space of a storage unit for a heading record of a sorted string should always be occupied by a heading record of the remaining sorted string of records. In other words, a string of records in storage should shift one record or address space forward by each output in order to keep the sort sequence. It is vital to maintain the sort sequence of a sorted string of records in storage and to keep outputting a heading record without a break. In this respect, some measures or mechanisms have to be taken or considered to solve the problem.
A two-way merge sort is discussed hereinafter in terms of processing timing. Generally, a processing unit in data sorting can be a record, word or byte. The conventional art employs record based one-word processing. FIG. 19 shows a timing diagram illustrating record based one-word processing between neighboring local processors in a two-way merge sort operation.
According to FIG. 19, a record consists of two fields: a data section consisting of a certain number of words and a two-word pointer. Each word has three cycles: a read cycle R0, a read cycle R1 and a write cycle W. A two-way merge sort in accordance with the record based one-word processing basically works word by word through a record. A two-way merge sort should access three storage units, for a comparison in the merge sort step, including the local memory, the internal buffer in the local processor and the line buffer. In other words, the local processor inputs one word or record each from the two storage units for comparison in the read cycles R0 and R1 respectively, and outputs one of the two words or records as a comparison result in the write cycle W. Thus, a resulting string of records from each pipeline stage are in order on a word basis.
As stated hereinbefore, the conventional hardware merge sorter is generally configured with linearly ordered cascaded pipeline stages including a local processor and a responsive local memory which has twice a storage capacity as that of the local memory of the preceding pipeline stage. When the hardware merge sorter has n number of pipeline stages, a local memory in the last pipeline stage has a storage capacity of 2.sup.n-1 number of records, which accounts for a half of the total storage capacity of the local memories. According to the conventional art, the storage capacity of the local memory in the last pipeline stage limits the maximum number of records sortable in the conventional hardware merge sorter. In other words the conventional hardware merge sorter can only sort twice the amount of data as that of the storage capacity of the local memory in the last pipeline stage. This can simply be interpreted that there would be no ceiling for the amount of records sortable in the conventional sorting system as long as the total storage capacity of the local memories can expand. Theoretically tills is possible even in terms of a high-speed and efficient sorting. In reality, however, unlimited expansion of the pipeline stages including the local memories or the size of the hardware merge sorter is impossible in a computing system from an architectural or packaging viewpoint. The number of records exceeding the ceiling, in fact, have to be processed on a software basis. This presents a bottleneck and limits high-speed and efficient sorting.